题目大意
给出每种地雷布置的区间,求某一区间的地雷总数
思路
1.(错误示例)用线段树维护区间地雷个数及区间单点地雷数最大值,每次给某一区间地雷均+1,每次再查询区间中单个点最大地雷数(因为每次铺的地雷都不一样)
缺陷:可能同一区间中存在地雷种类不同(例如存在两点地雷数相同,但是铺的地雷不完全相同)
2.用线段树维护区间铺地雷的起点及终点个数,运用差分的思想,区间地雷种类数=[1,r]区间的起点个数-[1,l-1]区间的终点个数
例:设1为起点 2为终点 0为非终点起点
1 | 1 1 0 1 0 2 1 1 0 1 2 0 2 1 2 0 2 0 2 0 0 0 0 2 |
[4,12]区间内的地雷总数为 6-0=6个
代码:
1 |
|